package com.company.algo.DichotomousSearch;

public class ArrangingCoins {
    //迭代
    public int arrangeCoins1(int n) {
        for(int i = 1; i<=n ; i++){
            n = n - i;
            if(n <= i) return i;
        }
        return 0;
    }

    //二分
    public int arrangeCoins2(int n) {
        int l = 0, r = n;
        while (l <= r){
            int mid = (l+r)/2;
            int cost = ((1+mid)*mid)/2;
            if (cost == n) return mid;
            else if (cost > n) r = mid - 1;
            else l = mid + 1;
        }
        return r;
    }

    /**
     * 牛顿法
     * (x+n/x)/2 -> sqrt(n)
     * 此时目标是查找 ((1+x)*x)/2 = n -> x+x^2 = 2n
     *  -> x = sqrt(2n - x)
     *  将n替换为 2n-x
     */
    public int arrangeCoins3(int n) {
        if (n == 0) return 0;
        return (int)sqrt(n,n);
    }

    private double sqrt(double x, double n) {
        double ret = (x+(2*n-x)/x)/2;
        if (x  == ret) return x;
        else return sqrt(ret,n);
    }


    public static void main(String[] args) {
        ArrangingCoins Main = new ArrangingCoins();
        System.out.println(Main.arrangeCoins3(5));
    }
}
